package topic.a_array.a_erfen;

/*
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，
返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素
 */
public class SearchInsert_35 {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 6};
        System.out.println(search(arr, 7));
        System.out.println(method(arr, 4));
    }

    public static int method(int[] s, int target) {
        int len=s.length;
        for (int i = 0; i < len; i++) {
            if (s[i]>=target) return i;
        }
        return len;
    }


    /*
    二分
     */
    public static int search(int[] s, int target) {
        int len = s.length;
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            int mid = left + ((right - left) / 2);
            if (s[mid] > target) {
                right = mid - 1;
            } else if (s[mid] < target) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return right + 1;
    }
}
